#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void printVector(const vector<int>& v)
{
    for(auto e : v)
        cout << e << " ";
    cout << endl;
}

/*返回a[left],a[right],a[mid]的中间值的下标*/
int getMidIndex(vector<int> &a, int left, int right)
{
    int m = (left + right) / 2, l = left, r = right;
    // 穷举所有情况即可
    if(a[l] > a[m])
        if(a[m] > a[r])
            return m;
        else if(a[r] > a[l])
            return l;
        else
            return r;
    else //a[l] < a[m]
        if(a[m] < a[r])
            return m;
        else if(a[r] < a[l])
            return l;
        else
            return r;
}

/*
    将数组某区间分为两部分，左边比key小，右边比key大。
    返回keyi，
    此时[left, keyi-1]比key小，[keyi+1,right]比key大
*/
int partSort(vector<int> &a, int left, int right)
{
    // 优化：三数取中，让key尽可能是数组中居中的值
    int midi = getMidIndex(a, left, right);
    std::swap(a[left], a[midi]);

    int l = left, r = right;
    int keyi = left; //左边做key，右边先走
    while(l < r)
    {
        // 右边先走，走到比key小的停下来
        while(l < r && a[r] >= a[keyi])
            --r;
        // 左边走，走到比key大的停下来
        while(l < r && a[l] <= a[keyi])
            ++l;
        // 把a[l]和a[r]交换，使大的换到右边，小的换到左边
        std::swap(a[l], a[r]);
    }
    // 此时l和r相遇，相遇点即为keyi
    std::swap(a[keyi], a[l]);
    keyi = l;
    return keyi;
}

int partSort2(vector<int> &a, int left, int right)
{
    // 优化：三数取中，让key尽可能是数组中居中的值
    int midi = getMidIndex(a, left, right);
    std::swap(a[left], a[midi]);

    int l = left, r = right;
    int keyi = left; // 左边做key，右边先走
    int key = a[keyi];
    while(l < r)
    {
        // 右边找小，填到左边的坑里，填完之后自己又变成坑
        while(l < r && a[r] >= a[keyi])
            --r;
        a[keyi] = a[r];
        keyi = r;

        // 左边找大，填到右边的坑里，填完之后自己又变成坑
        while(l < r && a[l] <= a[keyi])
            ++l;
        a[keyi] = a[l];
        keyi = l;
    }
    a[keyi] = key; // 填上最后的坑
    return keyi;
}

/*快慢指针法*/
int partSort3(vector<int> &a, int left, int right)
{
    // 优化：三数取中，让key尽可能是数组中居中的值
    int mid = getMidIndex(a, left, right);
    std::swap(a[left], a[mid]);

    int pre = left, cur = left + 1, keyi = left;
    while(cur <= right)
    {
        // cur找到比key小的，然后与a[++pre]交换
        // 表现为小的往前翻，大的往后甩
        if(a[cur] < a[keyi])
            if(++pre != cur)
                std::swap(a[pre], a[cur]);
        ++cur;
    }
    std::swap(a[pre], a[keyi]); // 最后慢指针就是keyi
    keyi = pre;
    return keyi;
}

/*递归完成快速排序*/
void _quickSort(vector<int> &a, int left, int right)
{
    if (left >= right)
        return;

    // 优化：当数组大小比较小时，再继续递归效率其实不高，不如换成其他排序
    // if(right - left + 1 < 15)
    // {
    //     insertSort(a, left, right); //插入排序
    //     return;
    // }
    
    int keyi = partSort3(a, left, right);
    cout << "keyi : " << keyi << "\t";
    printVector(a);
    _quickSort(a, left, keyi - 1); //对区间[left, keyi-1]排序
    _quickSort(a, keyi + 1, right); //对区间[keyi+1, right]排序
}

/*随机取key*/
int getRamdomKey(const vector<int>& a, int left, int right)
{
    int r = rand();
    return a[left + r % (right - left + 1)];
}

/*继续优化：随机取key + 数组分为三块*/
void _qsort(vector<int>& a, int left, int right)
{
    if(left >= right) return;
    
    int key = getRamdomKey(a, left, right);
    
    // 1.数组分成三块: 左边比key小，中间等于key，右边比key大
    int i = left, l = left - 1, r = right + 1;
    while(i < r)
    {
        if(a[i] < key)
            std::swap(a[i++], a[++l]);
        else if(a[i] > key)
            std::swap(a[i], a[--r]);
        else
            ++i;
    }
    // [left, l] [l+1, r-1] [r, right]
    // 2.对左边和右边递归
    _qsort(a, left, l);
    _qsort(a, r, right);
}

/*对数组a进行快速排序*/
void quickSort(vector<int> &a)
{
    srand(time(NULL));
    return _qsort(a, 0, a.size() - 1);
}

/*非递归完成对数组a的快速排序*/
void quickSortNotR(vector<int> &a)
{
    stack<int> st;
    int n = a.size();
    st.push(0);
    st.push(n-1);
    while(!st.empty())
    {
        // 先拿右端点，再拿左端点
        int right = st.top(); st.pop();
        int left = st.top(); st.pop();

        // 将数组划分为三区间: [left, keyi-1] keyi [keyi+1, right]
        int keyi = partSort3(a, left, right);

        // 放进去时，先放左端点，后放右端点
        if(left < keyi-1)
        {
            st.push(left);
            st.push(keyi-1);
        }
        if(keyi+1 < right)
        {
            st.push(keyi+1);
            st.push(right);
        }
    }
}


int main()
{
    // vector<int> a = {0, 2, 1};
    // int midi = getMidIndex(a, 0, 2);
    // cout << midi << endl;

    vector<int> a = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8, 13, 0,-1,-4,1,33,2,2,3,3,3};
    printVector(a);

    quickSort(a);

    printVector(a);

    return 0;
}